import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2022-10-28
 * Time: 11:04
 */


public class TestHeap {
    public static void main(String[] args) {
        MyPriorityQueue heap = new MyPriorityQueue();
        int[] array = {1,8,6,2,5,4,7,3};
        heap.addElem(array);
        heap.createMaxheap();
        heap.disPlay();
        System.out.println("===");
//
//        heap.offer(80);
//        int x = heap.pop();
//        heap.disPlay();


//        MyHeapSort myHeapSort = new MyHeapSort();
//        myHeapSort.addElem(array);
//        myHeapSort.createMaxheap();
//        myHeapSort.heapSort();
//        myHeapSort.disPlay();
    }


    public static class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

    public static void main2(String[] args) {
        /**
         *   如果 a - b 的结果小于 0，则表示 a 小于 b，即 a 在前、b 在后 ( 小根堆 )
         *   如果 a - b 的结果等于 0，则表示 a 等于 b，顺序不变。
         *   如果 a - b 的结果大于 0，则表示 a 大于 b，即 b 在前、a 在后. ( 大根堆 )
         */
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);
        priorityQueue.offer(15);
        priorityQueue.offer(3);
        priorityQueue.offer(12);

        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());

        System.out.println("================");

        // 匿名内部类的比较器
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        priorityQueue1.offer(15);
        priorityQueue1.offer(3);
        priorityQueue1.offer(12);

        System.out.println(priorityQueue1.poll());
        System.out.println(priorityQueue1.poll());
        System.out.println(priorityQueue1.poll());


        System.out.println("================");
        // 传入自定义的比较器实现 Comparator 比较器
        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue(new MyComparator());
        priorityQueue2.offer(15);
        priorityQueue2.offer(3);
        priorityQueue2.offer(12);

        System.out.println(priorityQueue2.poll());
        System.out.println(priorityQueue2.poll());
        System.out.println(priorityQueue2.poll());
        System.out.println("-===");
        int[] arr = {1, 3, 5, 7, 2, 4, 6, 8};
        TestHeap testHeap = new TestHeap();
        int[] tmp = testHeap.smallestK(arr, 4);
        System.out.println(Arrays.toString(tmp));
    }

    /**
     * top 问题解决最小 K 个数
     * 时间复杂度为 : 建立容量为 K 的堆, O(K)
     *              遍历剩下的 n - k 个元素, 每个元素向下调整, O( (n-k) * logK )
     *              最终时间复杂度约为 : O(nlogK)
     *
     * TODO : 第 K 个最小的元素为此时堆顶元素
     * @param arr 提供的数组
     * @param k 前 K 个数
     * @return 前 K 个最小数的数组
     */
    public int[] smallestK(int[] arr, int k) {

        // 预处理, 防止指定容量建堆失败
        if (arr == null || k <= 0) {
            return new int[0];
        }

        // 建立容量为 k 的大根堆, 并把前 K 个元素放进堆中
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (a, b) -> b - a);

        for (int x : arr) {
            // 堆中没有元素或者不足 K 个的时候, 将其直接加入大根堆
            if (maxHeap.size() < k) {
                maxHeap.offer(x);
            } else {
                // 已经有 K 个元素了, 将堆顶元素和下一个元素进行比较
                // 下一个元素如果比堆顶小, 则出堆顶元素, 如当前元素

                int tmp = maxHeap.peek();
                if (tmp > x) {
                    maxHeap.poll();
                    maxHeap.offer(x);
                }
            }
        }

        // 此时弹出以后, 当前堆中就是数组中前 K 个最小的元素, 并且堆顶为这 K 个最小元素中的最大那个
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }

        return tmp;
    }
}
